#include <stdio.h>

// 标准二分查找（迭代实现）
int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // 未找到
}

// 查找第一个等于target的元素
int firstOccurrence(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1; // 继续在左半部分查找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

// 测试函数
int main() {
    int arr[] = {2, 4, 6, 8, 10, 12, 14, 16};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    
    int index = binarySearch(arr, size, target);
    if (index != -1) {
        printf("Element %d found at index %d\n", target, index);
    } else {
        printf("Element %d not found\n", target);
    }
    
    // 测试重复元素的情况
    int dupArr[] = {1, 2, 2, 2, 3, 4, 5};
    int dupSize = sizeof(dupArr) / sizeof(dupArr[0]);
    
    int firstIndex = firstOccurrence(dupArr, dupSize, 2);
    printf("First occurrence of 2 is at index %d\n", firstIndex);
    
    return 0;
}